#include <stdio.h>

//图的边的结构体(也可以用来表示树)
struct LinkList
{
    //节点编号
    int index;
    //所有连接节点的边 包括根节点
    LinkList* next;
    LinkList* pre;
};

LinkList* newLinkList(int value)
{
    LinkList* newItem=new LinkList;
    newItem->index=value;
    newItem->next=NULL;
    newItem->pre=NULL;
    return newItem;
}

void deleteLinkList(LinkList* l)
{
    LinkList* next=l;
    while (next!=NULL)
    {
        LinkList* now=next->next;
        delete next;
        next=now;
    }
}


//添加单项边
void addSinglEv(LinkList** ev,int start,int end)
{
    LinkList* l=newLinkList(end);

    if(ev[start]==NULL)
    {
        ev[start]=l;
    }
    else{
        l->next=ev[start];
        ev[start]=l;
    }
}

void addLinkList(LinkList** ev,int index,LinkList* l)
{
    if(ev[index]==NULL)
    {
        ev[index]=l;
    }
    else{
        l->next=ev[index];
        ev[index]->pre=l;
        ev[index]=l;
    }
}

//添加双向边
void addEv(LinkList** ev,int start,int end){
    //添加双向边
    LinkList* l=newLinkList(end);
    addLinkList(ev,start,l);

    l=newLinkList(start);
    addLinkList(ev,end,l);
}

//链表添加新的节点
LinkList* addItemEnd(LinkList* l,LinkList* newItem)
{
    if(l==NULL)
    {
        l=newItem;   
    }
    else{
        l->next=newItem;
    }
    return newItem;
}


//无限长度的队列 必须要用链表实现
struct Queue
{
    LinkList* start; //队列起点
    LinkList* end;   //队列终点
    int size;//队列元素个数
};

Queue* newQueue()
{
    Queue* q=new Queue;
    q->size=0;
    q->start=NULL;
    q->end=NULL;
    return q;
}

//清空队列
void deleteQueue(Queue* q)
{
    deleteLinkList(q->start);
    delete q;
}

//入队
void inqueue(Queue* q,LinkList* newItem){
    LinkList* end=addItemEnd(q->end,newItem);
    q->end=end;
    if(q->start==NULL)
    {
        q->start=end;
    }
    q->size++;
}

//出队
LinkList* dequeen(Queue* q){
    if(q->start==NULL)
    {
        return NULL;
    }
    else{
        LinkList* l=q->start;
        q->start=l->next;
        q->size--;
        return l;
    }
}

//队列元素多少
int sizeOfQueue(Queue* q)
{
    return q->size;
}

//队列是否为空
int isEmpQueue(Queue* q)
{
    return q->size==0;
}

const int modNum=100003;

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    int i;
    LinkList** ev=new LinkList*[n];
    int* result=new int[n];
    int* step=new int[n];
    int* bj=new int[n];
    for(i=0;i<n;i++)
    {
        ev[i]=NULL;
        result[i]=0;
        step[i]=0;
        bj[i]=1;
    }

    int tmp1,tmp2;
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&tmp1,&tmp2);
        tmp1--;
        tmp2--;

        addEv(ev,tmp1,tmp2);
    }
   

    Queue* q=newQueue();
    LinkList* l=newLinkList(0);
    result[0]=1;
    step[0]=1;
    bj[0]=0;
    inqueue(q,l);
    
    while (!isEmpQueue(q))
    {
        LinkList* l=dequeen(q);
        int index=l->index;
        int nextStep=step[index]+1;
        delete l;

        l=ev[index];
        while (l!=NULL)
        {
            int newIndex=l->index;
            //没有入队的入队
            if(bj[newIndex])
            {
                LinkList* l=newLinkList(newIndex);
                bj[newIndex]=0;
                inqueue(q,l);
            }
            if(step[newIndex]==0||step[newIndex]>nextStep)
            {
                step[newIndex]=nextStep;
                result[newIndex]=result[index];
            }
            else if(step[newIndex]==nextStep)
            {
                result[newIndex]=(result[newIndex]+result[index])%modNum;
            }
            
            l=l->next;
        }
        
    }
    
    for(i=0;i<n;i++)
    {
        printf("%d\n",result[i]);
    }

    for(i=0;i<n;i++)
    {
        deleteLinkList(ev[i]);
    }
    delete ev;
    delete result;
    delete step;
    delete bj;

    delete q;
    return 0;
}

